package edu.rit.checkers;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * A ConfigTree is a tree made up of ConfigNodes arranged in a tree fashion.
 * ConfigNodes have children who have children, so forth and so on. A ConfigTree
 * can be pruned using the Alpha-Beta algorithm and can be grown based on a
 * desired tree size or for a max amount of time.  The tree is explored using
 * depth first search to the max depth.  If the entire tree has been explored
 * to the max depth then the trees max depth can be increased to allow more
 * searching.  For parallel exploring create child ConfigTrees using ConfigNodes
 * from a parent ConfigTree as the root for the child ConfigTrees then once
 * the sub trees are done being explored they can be merged to the parent
 * ConfigTree.  Keep in mind that logically because of the child parent relation
 * all of the trees are already one tree the difference is the data kept about
 * the tree such as the amount of added nodes and what is used as the root node
 * for alpha-beta prunning.
 * 
 * @author Ian Tewksbury (ict8574@rit.edu)
 */
public class ConfigTree {
	
	/**
	 * So that alpha-beta is not performed on an overly large tree
	 */
	private final long MAX_ADDED_NODES_BEFORE_AB = 10000;

	//CACHE INTERFERENCE: avoidance
	//SOURCE: Taken from examples in Parallel Java Library
	@SuppressWarnings("unused")
	private long pad0, pad1, pad2, pad3, pad4, pad5, pad6, pad7;
	@SuppressWarnings("unused")
	private long pad8, pad9, pada, padb, padc, padd, pade, padf;

	/**
	 * The root of this tree
	 */
	private ConfigNode root;
	
	/**
	 * The current max depth this tree will be explored too
	 */
	private int maxDepth;
	
	/**
	 * The unexplored nodes added to this tree, an unexplored node
	 * is one whos children have not yet been generated and added
	 * to the tree
	 */
	private SortedSet<ConfigNode> unexploredNodes;
	
	/**
	 * These are nodes that are the children of nodes at the max depth
	 * when the max depth of the tree is increased these nodes will be
	 * turned into unexplored nodes
	 */
	private List<ConfigNode> nextDepthIncreaseNodes;
	
	/**
	 * The number of total nodes added to this tree
	 */
	private long addedNodes;
	
	/**
	 * The number of nodes pruned from this tree using a-b
	 */
	private long prunedNodes;
	
	/**
	 * The level of the deepest node in the tree
	 */
	private int deepistNode;
	
	/**
	 * The last calculated a-b score for this tree
	 */
	private double alphaBetaScore;

	/**
	 * Creates a ConfigTree with the given initial max depth and with the given
	 * root node.
	 * 
	 * @param initMaxDepth the initial max depth of this tree
	 * @param rootNode the root node of this tree
	 */
	public ConfigTree(int initMaxDepth, ConfigNode rootNode) {
		this.root = rootNode;
		this.maxDepth = initMaxDepth;
		this.addedNodes = 0;
		this.prunedNodes = 0;
		this.deepistNode = this.root.depth;
		this.alphaBetaScore = 0;
		
		/*
		 * Unexplored nodes have to be explored in depth first order,
		 * hence the sorted tree set
		 */
		this.unexploredNodes = new TreeSet<ConfigNode>(
			/**
			 * assign lowest left nodes first, depth first
			 */
			new Comparator<ConfigNode>() {
				public int compare(ConfigNode o1, ConfigNode o2) {
					//Assign lowest nodes first
					int retVal = o2.depth - o1.depth;
					if(retVal == 0) {
						//explore furtherest left nodes first
						retVal = (int)(o1.nodeNum - o2.nodeNum);
					}
					
					return retVal;
				}
				
			});
		
		//the root node is the first unexplored node
		this.unexploredNodes.add(root);
		
		this.nextDepthIncreaseNodes = new ArrayList<ConfigNode>(1000000);
	}
	
	/**
	 * Increases the max depth of this tree allowing it to grow more
	 * 
	 * @param increaseAmount the amount to increase the max depth of the
	 * tree by
	 */
	public  void increaseMaxDepth(int increaseAmount) {
		this.maxDepth += increaseAmount;
		
		//this nodes have now officially been added to the tree
		this.addedNodes += this.nextDepthIncreaseNodes.size();
		
		this.unexploredNodes.addAll(this.nextDepthIncreaseNodes);
		this.nextDepthIncreaseNodes.clear();
	}
	
	/**
	 * Grow the tree up to the max depth or the stop time, whichever
	 * comes first
	 * 
	 * @param stopTime the global time in milliseconds to stop growing
	 * the tree
	 */
	public void growTreeToCurrDepthLimit(long stopTime) {
		while(this.hasUnexploredNodes() &&
			System.currentTimeMillis() < stopTime) {
			
			long startAddedNodes = this.addedNodes;
			while(this.hasUnexploredNodes() &&
				(this.addedNodes-startAddedNodes) < MAX_ADDED_NODES_BEFORE_AB &&
				System.currentTimeMillis() < stopTime) {
				
				ConfigNode current = this.getNextUnexploredNode();
				current.generateChildren();
				this.addNodes(current.children);
			}
				
			this.alphaBeta();
		}
	}
	
	/**
	 * Grow the tree to a specific size. Useful when you need so many
	 * nodes to assign to different threads.
	 * 
	 * @param size the min size to grow the tree too, could grow larger
	 */
	public void growTreeToSize(int size) {
		while(this.unexploredNodes.size() < size) {
			ConfigNode current = this.getNextUnexploredNode();
			current.generateChildren();
			this.addNodes(current.children);
		}
	}
	
	/**
	 * Merges a list of trees that have roots from this tree into this tree.
	 * Logically this trees are already connected, this just updates all the
	 * fields of this tree.
	 * 
	 * @param childTrees the child trees to merge into this tree
	 */
	public void mergChildTrees(List<ConfigTree> childTrees) {
		for(ConfigTree childTree : childTrees) {
			if(childTree.maxDepth > this.maxDepth) {
				this.maxDepth = childTree.maxDepth;
			}
			
			if(childTree.deepistNode > this.deepistNode) {
				this.deepistNode = childTree.deepistNode;
			}
			
			this.unexploredNodes.addAll(childTree.unexploredNodes);
			
			if(childTree.maxDepth < this.maxDepth) {
				this.unexploredNodes.addAll(childTree.nextDepthIncreaseNodes);
			} else {
				this.nextDepthIncreaseNodes.addAll(
					childTree.nextDepthIncreaseNodes);
			}
			
			this.addedNodes += childTree.addedNodes;
			this.prunedNodes += childTree.prunedNodes;
		}
	}
	
	/**
	 * Get the size of this tree, the size is the added nodes minus the
	 * pruned nodes.
	 * 
	 * @return the size of this tree
	 */
	public long size() {
		return this.addedNodes - this.prunedNodes;
	}
	
	/**
	 * Get the number of nodes added to this tree
	 * 
	 * @return the number of nodes added to this tree
	 */
	public long getAddedNodes() {
		return this.addedNodes;
	}
	
	/**
	 * Get the last a-b score calculated by alphaBeta
	 * 
	 * @return the last a-b score calculated by alphaBeta
	 */
	public double getLastAlphaBetaScore() {
		return this.alphaBetaScore;
	}
	
	/**
	 * Run the alpha-beta pruning algorithm on this tree to prun out
	 * unneccissary nodes.
	 */
	public  void alphaBeta() {
		this.alphaBetaScore = 
			alphaBeta(this.root, Double.NEGATIVE_INFINITY,
					Double.POSITIVE_INFINITY, this.maxDepth);
	}
	
	@Override
	public String toString() {
		String s = "Tree:";
		s += "\n  Depth:";
		s += "\n    Max: " + this.maxDepth;
		s += "\n    Current: " + this.deepistNode;
		s += "\n  Size: " + this.size();
		s += "\n    Added Nodes: " + this.addedNodes;
		s += "\n    Pruned Nodes: " + this.prunedNodes;
		s += "\n  Unexplored Nodes: " + this.unexploredNodes.size();
		s += "\n  Max Depth Nodes: " + this.nextDepthIncreaseNodes.size();
		s += "\n  Last Alpha-Beta Score: " + this.getLastAlphaBetaScore();
		
		return s;
	}

/*************************
* PRIVATE HELPER METHODS *
*************************/
	
	/**
	 * Returns whether this tree has any unexplored nodes
	 * 
	 * @return true if this tree has unexplored nodes, false otherwise
	 */
	private boolean hasUnexploredNodes() {
		return !this.unexploredNodes.isEmpty();
	}
	
	/**
	 * Returns the next unexplored node or null if there are none
	 * 
	 * @return the next unexplored node or null if there are none
	 */
	public ConfigNode getNextUnexploredNode() {
		ConfigNode retVal = null;
		
		if(this.hasUnexploredNodes()) {
			retVal = this.unexploredNodes.first();
			this.unexploredNodes.remove(retVal);
		}

		return retVal;
	}
	
	/**
	 * Attempt to add a list of nodes to this tree using the addNode function,
	 * see addNode function for more detail.
	 * 
	 * @param nodes the nodes to add to this tree using the addNode function
	 * @return true if all nodes were added, false otherwise
	 */
	private boolean addNodes(List<ConfigNode> nodes) {
		boolean allAdded = true;
		
		for(ConfigNode node : nodes) {
			allAdded = allAdded && this.addNode(node);
		}
		
		return allAdded;
	}
	
	/**
	 * Attempt to add a node to this tree.  If the node is less then or equal to
	 * the max depth of this tree then the node will be added as unexplored,
	 * else if the node is one level deeper it will be added as a node in the
	 * next depth nodes but not official added to the tree because it is to
	 * deep.  Any node deeper then one level deeper then max depth will not 
	 * be added and cause this function to return false.
	 * 
	 * @param node the node to attempt to add to this tree
	 * @return true if this node was added to the tree, false otherwise
	 */
	private boolean addNode(ConfigNode node) {
		boolean added = false;
		
		if(node.depth <= this.maxDepth) {
			++this.addedNodes;
			this.unexploredNodes.add(node);
			
			if(node.depth > this.deepistNode) {
				this.deepistNode = node.depth;
			}
			
			added = true;
		} else if(node.depth == this.maxDepth+1) {
			this.nextDepthIncreaseNodes.add(node);
		}
		
		return added;
	}
	
	/**
	 * The recursive implementation of alphaBeta
	 * 
	 * @param currNode the current node
	 * @param alpha the alpha value
	 * @param beta the beta value
	 * @param maxDepth the max depth to alpha beta too
	 * @return the a-b score of the given current node
	 */
	private double alphaBeta(ConfigNode currNode, double alpha, double beta,
		int maxDepth) {
		
		List<ConfigNode> children = currNode.children;
		
		//if at max depth or game over (either winning player or no possible
		//	moves) then return score of move
		if(currNode.depth == maxDepth || children == null ||
			children.isEmpty() || currNode.isFinalConfig()) {

			return currNode.getScore();
		}
		
		Collections.sort(children,
				/**
				 * Comparator to place high scores first for A-B optimization
				 */
				new Comparator<ConfigNode>() {
					/**
					 * 
					 * @param o1
					 * @param o2
					 * @return
					 */
					public int compare(ConfigNode o1, ConfigNode o2) {
						return o2.getScore() - o1.getScore();
					}
				}
			);
		
		double score;
		boolean cutOff = false;
		List<ConfigNode> cutOffChildren = new ArrayList<ConfigNode>();
		//if max's turn
		if(currNode.getPlayer() == 2) {
			double newAlpha = alpha;
			for(ConfigNode childNode : children) {
				if(!cutOff) {
					score = alphaBeta(childNode, newAlpha, beta, maxDepth);
					if(score > newAlpha) {
						newAlpha = score; //we found better move
					}
					if(newAlpha >= beta) {
						cutOff = true;
					}
				} else {
					cutOffChildren.add(childNode);
				}
			}
			
			//we are cutting off all unneeded children
			this.removeChildren(currNode, cutOffChildren);
			
			return newAlpha; //our best move
		//if min's turn
		} else {
			double newBeta = beta;
			for(ConfigNode childNode : children) {
				if(!cutOff) {
					score = alphaBeta(childNode, alpha, newBeta, maxDepth);
					if(score < newBeta) {
						newBeta = score; //opponent found better move
					}
					if(alpha >= newBeta) {
						cutOff = true;
					}
				} else {
					cutOffChildren.add(childNode);
				}
			}
			
			//we are cutting off all unneeded children
			this.removeChildren(currNode, cutOffChildren);
			
			return newBeta; //opponents best move
		}
	}

	/**
	 * Removes the given children from the given parent and updates the tree
	 * data appropriately.
	 * 
	 * @param parent the parent to childrenToRemove
	 * @param childrenToRemove the children to remove from the tree who's parent
	 * is given as parent
	 */
	private void removeChildren(ConfigNode parent,
		List<ConfigNode> childrenToRemove) {
		
		if(parent.depth < this.maxDepth) {
			this.prunedNodes += childrenToRemove.size();
		
				
			for(ConfigNode child : childrenToRemove) {		
				//remove from unassigned nodes and max depth
				//	nodes if it is there
				this.unexploredNodes.remove(child);
				this.nextDepthIncreaseNodes.remove(child);
				
				//have to recursively remove all children
				this.removeChildren(child, child.children);
			}
			
			//remove from parent
			parent.children.removeAll(childrenToRemove);
		}
	}
			
}